package sort.shellsort;

import sort.generator.ArrayGenerator;
import sort.helper.SortingHelper;

/**
 * @author XY
 * @version 1.0.0
 * @ClassName ShellSort.java
 * @createTime 2021年12月12日 08:53:00
 */
public class ShellSort {

    private ShellSort(){

    }

    public static <E extends Comparable<E>>  void sort(E[] data){
        //选定一个区间
        int h  = data.length/2;
        while(h>=1){
            //首先在区间个数内进行循环
            for(int i =0 ;i<h ;i ++){
                //分组的插入排序，以区间进行分组
                for(int n = i + h ; n<data.length; n+=h){
                    E temp = data[n];
                    int j ;
                    for(j = n; j-h >= 0 && temp.compareTo(data[j-h])<0;j-=h){
                        data[j] = data[j-h];
                    }
                    data[j] = temp;
                }
            }
            h = h/2;
        }
        System.out.println(1);
    }

    //减少一重循环实现希尔排序
    public static <E extends Comparable<E>>  void sort2(E[] data){
        //选定一个区间
        int h  = data.length/2;
        while(h>=1){
            //对 data[h,n]进行插入排序,从h开始每个元素都与上一个步长为h的元素进行插入排序，h以前的元素当i++的时候也会遍历到
            for(int i = h ; i<data.length; i++){
                E temp = data[i];
                int j ;
                //插入排序的步长为h
                for(j = i; j-h >= 0 && temp.compareTo(data[j-h])<0;j-=h){
                    data[j] = data[j-h];
                }
                data[j] = temp;
            }
            h = h/2;
        }
        System.out.println(1);
    }

    //步长序列优化，初始h的取值
    public static <E extends Comparable<E>>  void sort3(E[] data){
        int h  = 1;
        //初始化h的值变化
        while(h<data.length){
            h = h * 3 + 1;
        }
        while(h>=1){
            //对 data[h,n]进行插入排序,从h开始每个元素都与上一个步长为h的元素进行插入排序，h以前的元素当i++的时候也会遍历到
            for(int i = h ; i<data.length; i++){
                E temp = data[i];
                int j ;
                //插入排序的步长为h
                for(j = i; j-h >= 0 && temp.compareTo(data[j-h])<0;j-=h){
                    data[j] = data[j-h];
                }
                data[j] = temp;
            }
            h = h/3;
        }
        System.out.println(1);
    }

    public static void main(String[] args) {
        int n = 100000;
        Integer[] integers = ArrayGenerator.generateRandomArray(n, n);
        SortingHelper.sortTest("ShellSort",integers);
    }
}
